package common;

import java.math.BigInteger;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
public class PrimeGen {

	public static Set<BigInteger> getFactors(BigInteger myNum){

		Set<BigInteger> factors = new HashSet<BigInteger>();

		//int n = myNum.intValue();
		BigInteger number = new BigInteger(myNum.toByteArray());
		//System.out.print("The prime factorization of " + number + " is: ");

		// for each potential factor i
		for (BigInteger i = new BigInteger("2"); i.compareTo(number)==-1 ; i=i.add(BigInteger.ONE)) {
//System.out.println("current i: "+i);
			// if i is a factor of N, repeatedly divide it out
			BigInteger[] devision = number.divideAndRemainder(i);
			while (devision[1].equals(BigInteger.ZERO)) {
				factors.add(new BigInteger(""+i));
				//System.out.print(i + " "); 
				number = devision[0];
	//System.out.println("factors: "+ factors + ", devision[0]: "+ devision[0]+ ", devision[1]: "+ devision[1]+ ", number: "+ number);
				devision = number.divideAndRemainder(i);
				//System.out.println("devision: "+ devision[0] +" "+devision[1]);
			}
	//		System.out.println("number: "+number);
		//	System.out.println("i: "+i);
			
			//System.out.println(i.compareTo(number));
		}

		// if biggest factor occurs only once, n > 1
		if (number.compareTo(BigInteger.ONE)==1) {
			factors.add(new BigInteger(""+number));
			//System.out.println(number);
		}
		else       
			System.out.println();
		//System.out.println("Done factoring");
		return factors;

	}

	public static int  computeCreatorFact(BigInteger somePrime) {

		boolean isGenerator;	
		Set<BigInteger> factors = getFactors(somePrime.subtract(BigInteger.ONE));
		//Set<BigInteger> factors = new HashSet<BigInteger>();
		//factors.add(new BigInteger("4"));
		for (Iterator<BigInteger> iterator = factors.iterator(); iterator.hasNext();) {
			BigInteger factor = iterator.next();
			isGenerator  = true;
			for (int i = 1; i < somePrime.intValue()-2; i++) {
				if (factor.modPow(new BigInteger(""+i),somePrime).intValue() == 1){
					isGenerator  = false;
					break;
				}
					
			}
			
			isGenerator = isGenerator && 
				(factor.modPow(somePrime.subtract(BigInteger.ONE),somePrime).intValue() == 1);
			
			
			
			if (isGenerator)
				return factor.intValue();
		}
		
		
		return -1; // shouldn't get here...
	}
	
	public static int  computeCreator(BigInteger somePrime) {

		boolean isGenerator;
		BigInteger genCandidate;
		
		for (int j=2; j < somePrime.intValue()-1 ; j++ ) {
			genCandidate = new BigInteger(""+j);
			isGenerator  = true;
			for (int i = 1; i < somePrime.intValue()-2; i++) {
				if (genCandidate.modPow(new BigInteger(""+i),somePrime).intValue() == 1){
					isGenerator  = false;
					break;
				}
					
			}
			
			isGenerator = isGenerator && 
				(genCandidate.modPow(somePrime.subtract(BigInteger.ONE),somePrime).intValue() == 1);
			
			
			
			if (isGenerator)
				return genCandidate.intValue();
		}
		
		
		return -1; // shouldn't get here...
	}
	
	
	
	




	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		//BigBigInteger bprime = new BigBigInteger(int bitLength, int certainty, Random rnd);
		//Random rnd = new Random();
		//BigBigInteger bprime = new BigBigInteger(1024, 3, rnd);

		//System.out.println("Mah Prime:" + bprime.toString());
		//System.out.println(computeCreatorFact(new BigInteger("1907")));
		System.out.println(computeCreatorFact(new BigInteger("439351292910452432574786963588089477522344331")));//439351292910452432574786963588089477522344331
		
	}

}
